/**
 * @a https://leetcode.cn/problems/number-of-islands/
 */

#include "../../common.h"

class Solution {
    vector<vector<bool>> visited;

    int numIslands_aux(const vector<vector<char>>& grid, int i, int j){
        static int dx[4] = {0,0,1,-1};
        static int dy[4] = {1,-1,0,0};
        if(visited[i][j] == true) return 0;
        
        visited[i][j] = true;
        queue<pair<int,int>> que;
        int row = grid.size(),col = grid[0].size();
        que.push({i,j});
        while(que.size()){
            auto [x,y] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i){
                int a = x + dx[i], b = y + dy[i];
                if(a >= 0 && a < row && b >= 0 && b < col && visited[a][b] == false && grid[a][b] == '1'){
                    visited[a][b] = true;
                    que.push({a,b});
                }
            }
        }
        return 1;
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if(row == 0) return 0;
        int col = grid[0].size();
        visited.resize(row);
        for(int i = 0; i < row; ++ i) visited[i].resize(col,false);
        int ret = 0;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(grid[i][j] == '1')
                    ret += numIslands_aux(grid, i,j);
            }
        }
        return ret;
    }
};